package org.xingole.leetcode.dp.knapsack;

import java.util.HashMap;
import java.util.Map;

/*
 * Problem: 
 * 
 * You are installing a billboard and want it to have the largest height. The 
 * billboard will have two steel supports, one on each side. Each steel support 
 * must be an equal height.
 * 
 * You are given a collection of 'rods' that can be welded together, if you have 
 * rods of lengths 1, 2, and 3, you can weld them together to make support of 
 * length 6.
 * 
 * Return the largest possible height of your billboard installation. 
 * If you cannot support the billboard, return 0.
 * 
 */

public class TallestBillboard {

     /*
      * Overview
      *
      * One possible approach to this problem is to generate all possible combinators of 
      * the rods and check which one satisfy the conditions.
      *
      * However, the number of possible combinators can grow exponentially with n, the
      * number of rods given as input, because each rod can be either added to the 1st
      * stand, 2nd stand or not be used at all.
      *
      * Approach: Dynamic Programming
      *
      * Instead, if we denote '+x', '-x', or '0' for each rod choices corresponding to 
      * 1st stand, 2nd stand and not used respectively, the ultimate target is to sum 
      * the whole to zero and keep the positive sum maixmum, denoted by 'score'. 
      *
      * 1. Determine the subproblem structure.
      *
      * Let dp[i][s] represents the maximum 'score' which can be achieved only considering
      * the rods[j] (i <= j < n), where 's' is the total sum by first (i - 1) choices.
      *
      * 2. Recursively solve the problem
      * 
      * Base case:
      *   If i = n, then the set of rods is empty, so we have only two situations:
      *      - dp[n][s] = 0,          if s = 0;
      *      - dp[n][s] = -infinity,  otherwise;
      * Inductive case:
      *    dp[i][s] = max(dp[i+1][s], dp[i+1][s-rods[i]], rods[i] + dp[i+1][s+rods[i]])
      * corresponding to above three cases.
      *
      */
     private static final int NEG_INF = Integer.MIN_VALUE / 3;

     private Map<State, Integer> memo;

     public int tallestBillboard(int[] rods) {
          memo = new HashMap<>();

          return dp(rods, 0, 0);

     }

     private int dp ( int[] rods, int i, int s ) {
          // Base case
          if ( i == rods.length ) {
               if ( s == 0 ) return 0;
               else          return NEG_INF;
          }

          State state = new State(i, s);
          if ( memo.containsKey( state ) ) return memo.get( state );

          // Recursive solve the problem.
          int score = 0;

          score = Math.max(
               dp(rods, i + 1, s),                            // not used 
               Math.max(
                    dp(rods, i + 1, s - rods[i]),           // 2nd stand
                    rods[i] + dp(rods, i + 1, s + rods[i] ) // 1st stand
               )
          );

          memo.put(state, score);

          return score;
     }

     private record State(int i, int s) {
     }

     public static void main(String[] args) {
          TallestBillboard tb = new TallestBillboard();

          int[] rods = null;

          // Exmaple 1:
          // Input: rods = [1, 2, 3, 6]
          // Expected: 6
          rods = new int[]{1, 2, 3, 6};
          System.out.println("Example 1 Output: " + tb.tallestBillboard(rods) );

          // Example 2:
          // Input: rods = [1, 2, 3, 4, 5, 6]
          // Expected: 10
          rods = new int[]{1, 2, 3, 4, 5, 6};
          System.out.println("Example 2 Output; " + tb.tallestBillboard(rods) );

          // Exmaple 3:
          // Input: rods = [1, 2]
          // Expected: 0
          rods = new int[]{1, 2};
          System.out.println("Exmaple 3 Output: " + tb.tallestBillboard(rods) );
     }

}
